// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

use std::collections::HashSet;
use std::hash::{Hash, Hasher};
use std::mem;

/// A generic set implementation that uses custom hash and equality functions.
pub struct CustomSet<T, H, E>
where
    T: Hash + Eq,
    H: Fn(&T) -> u64,
    E: Fn(&T, &T) -> bool,
{
    set: HashSet<T>,
    hash_fn: H,
    eq_fn: E,
}

impl<T, H, E> CustomSet<T, H, E>
where
    T: Hash + Eq,
    H: Fn(&T) -> u64,
    E: Fn(&T, &T) -> bool,
{
    /// Creates a new set with the given hash and equality functions.
    pub fn new(hash_fn: H, eq_fn: E) -> Self {
        CustomSet {
            set: HashSet::new(),
            hash_fn,
            eq_fn,
        }
    }

    /// Inserts a value into the set.
    pub fn insert(&mut self, value: T) -> bool {
        self.set.insert(value)
    }

    /// Checks if a value is in the set.
    pub fn contains(&self, value: &T) -> bool {
        self.set.contains(value)
    }

    /// Removes a value from the set.
    pub fn remove(&mut self, value: &T) -> bool {
        self.set.remove(value)
    }

    /// Returns the number of entries in the set.
    pub fn len(&self) -> usize {
        self.set.len()
    }

    /// Clears the set, removing all values.
    pub fn clear(&mut self) {
        self.set.clear();
    }
}

/// Generates a set with 10,000 string values.
pub fn generate_set() -> CustomSet<String, fn(&String) -> u64, fn(&String, &String) -> bool> {
    let mut set = CustomSet::new(string_hash, string_equal);
    for i in 0..10000 {
        let value = format!("{}", i);
        set.insert(value.clone());
        assert_eq!(set.len(), i + 1);
    }
    set
}

/// Tests the creation and freeing of a set.
#[test]
fn test_set_new_free() {
    let mut set = CustomSet::new(int_hash, int_equal);
    for i in 0..10000 {
        let value = i;
        set.insert(value);
    }
    assert_eq!(set.len(), 10000);
    set.clear();
}

/// Tests inserting values into a set.
#[test]
fn test_set_insert() {
    let mut set = CustomSet::new(int_hash, int_equal);
    let numbers1 = [1, 2, 3, 4, 5, 6];
    let numbers2 = [5, 6, 7, 8, 9, 10];
    for &num in numbers1.iter() {
        set.insert(num);
    }
    for &num in numbers2.iter() {
        set.insert(num);
    }
    assert_eq!(set.len(), 10);
}

/// Tests querying values in a set.
#[test]
fn test_set_query() {
    let set = generate_set();
    for i in 0..10000 {
        let value = format!("{}", i);
        assert!(set.contains(&value));
    }
    assert!(!set.contains("-1"));
    assert!(!set.contains("100001"));
}

/// Tests removing values from a set.
#[test]
fn test_set_remove() {
    let mut set = generate_set();
    let mut num_entries = set.len();
    assert_eq!(num_entries, 10000);
    for i in 4000..6000 {
        let value = format!("{}", i);
        assert!(set.contains(&value));
        assert!(set.remove(&value));
        assert_eq!(set.len(), num_entries - 1);
        assert!(!set.contains(&value));
        num_entries -= 1;
    }
    for i in -1000..-500 {
        let value = format!("{}", i);
        assert!(!set.remove(&value));
        assert_eq!(set.len(), num_entries);
    }
    for i in 50000..51000 {
        let value = format!("{}", i);
        assert!(!set.remove(&value));
        assert_eq!(set.len(), num_entries);
    }
}

/// Tests the union of two sets.
#[test]
fn test_set_union() {
    let mut set1 = CustomSet::new(int_hash, int_equal);
    let mut set2 = CustomSet::new(int_hash, int_equal);
    let numbers1 = [1, 2, 3, 4, 5, 6, 7];
    let numbers2 = [5, 6, 7, 8, 9, 10, 11];
    for &num in numbers1.iter() {
        set1.insert(num);
    }
    for &num in numbers2.iter() {
        set2.insert(num);
    }
    let mut result_set = CustomSet::new(int_hash, int_equal);
    for &num in set1.set.union(&set2.set) {
        result_set.insert(*num);
    }
    assert_eq!(result_set.len(), 11);
}

/// Tests the intersection of two sets.
#[test]
fn test_set_intersection() {
    let mut set1 = CustomSet::new(int_hash, int_equal);
    let mut set2 = CustomSet::new(int_hash, int_equal);
    let numbers1 = [1, 2, 3, 4, 5, 6, 7];
    let numbers2 = [5, 6, 7, 8, 9, 10, 11];
    for &num in numbers1.iter() {
        set1.insert(num);
    }
    for &num in numbers2.iter() {
        set2.insert(num);
    }
    let mut result_set = CustomSet::new(int_hash, int_equal);
    for &num in set1.set.intersection(&set2.set) {
        result_set.insert(*num);
    }
    assert_eq!(result_set.len(), 3);
}

/// Custom hash function for integers.
fn int_hash(value: &i32) -> u64 {
    *value as u64
}

/// Custom equality function for integers.
fn int_equal(a: &i32, b: &i32) -> bool {
    a == b
}

/// Custom hash function for strings.
fn string_hash(value: &String) -> u64 {
    let mut hasher = std::collections::hash_map::DefaultHasher::new();
    value.hash(&mut hasher);
    hasher.finish()
}

/// Custom equality function for strings.
fn string_equal(a: &String, b: &String) -> bool {
    a == b
}
